package algorithm.Sort;

import algorithm.Util.Examination;

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
       int [] arr = {12,6,5,4,3,2,1,2,52,44,155,157,15,177,135,122,852,300,100,125,120,4,50,13,120,
               3,2,1,2,52,44,155,157,15,177,135,12,6,5,4,3,12,6,5,4,3,2,1,2,52,44,155,157,15,177,135,122,852,300,100,125,120,4,50,13,120,
               3,2,1,2,52,44,155,157,15,177,135,12,6,5,4,3,12,6,5,4,3,2,1,2,52,44,155,157,15,177,135,122,852,300,100,125,120,4,50,13,120,
               3,2,1,2,52,44,155,157,15,177,135,12,6,5,4,3,12,6,5,4,3,2,1,2,52,44,155,157,15,177,135,122,852,300,100,125,120,4,50,13,120,
               3,2,1,2,52,44,155,157,15,177,135,12,6,5,4,3};
       Examination.start();
       arr = SelectionSort(arr);
       Examination.end();
       System.out.println(Arrays.toString(arr));
    }

    /**
     * 选择排序算法
     * @param arr 传入未排序数组
     * @return   返回有序数组
     */
    public static int [] SelectionSort(int [] arr){
        for (int i = 0; i < arr.length; i++) {
            //把arr[i]赋值给currMin记录为最小值
           int currMin = arr[i];
           //记录最小值的下标
           int minIndex = i;
           //内层循环把最小值和其他元素进行对比
            for (int j = i+1; j <arr.length ; j++) {
                if(currMin>arr[j]){
                    //如果最小值大于arr[j]元素，就令最小值等于这个元素，同时把最小下标改为j
                    currMin = arr[j];
                    minIndex = j;
                }
            }
            //内层循环完毕，判断最小值下标是否还等于i,如果不是则证明进行过替换，存在比arr[i]更小的元素
            if (minIndex != i){
                //这是令arr[minIndex]=arr[i],把arr[i]往后移动，完成当前循环最小元素查询
                arr[minIndex] = arr[i];
                //同时让arr[i]等于currMin，把最小元素往前提，至此完成元素调换
                arr[i] = currMin;
            }
        }
        return arr;
    }
}
